package com.bang.study.day02;

import com.bang.study.util.ArrayUtil;


/**
 * @Auther: Bang
 * @Date: 2019/9/21 0021 10:18
 * @Description: 归并排序(基于递归实现) 另一种方式基于迭代,即从底层到顶层归并(使用链表实现)
 * @描述: 1. 把长度为n的输入序列分成两个长度为n/2的子序列；
 * 2. 对这两个子序列分别采用归并排序；
 * 3. 将两个排序好的子序列合并成一个最终的排序序列
 * @算法分析: 最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)
 * 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。
 * 代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 * 若将两个有序表合并成一个有序表，称为2-路归并。 
 */
public class MergeSort {

    /**
     * 归并排序
     *
     * @param arr
     */
    public static void sort(Integer[] arr) {
//        mergeSort(arr, 0, arr.length - 1);


        // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        Integer[] tempArr = new Integer[arr.length];
        mergeSortV2(arr, 0, arr.length - 1, tempArr);
    }


    /**
     * 将arr [left,right] 拆分为左右子数组,并进行合并
     *
     * @param arr
     * @param left
     * @param right
     */
    static void mergeSort(Integer[] arr, int left, int right) {
        if (right <= left) {
            return;
        } else {
            int middle = left + (right - left) / 2;
            // 对左侧序列进行归并排序
            mergeSort(arr, left, middle);
            // 对右侧序列进行归并排序
            mergeSort(arr, middle + 1, right);
            // 合并两个子序列
            merge(arr, left, middle, right);
        }
    }

    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     *
     * @param arr    目标数组
     * @param left   左边界
     * @param middle 中间
     * @param right  右边界
     */
    static void merge(Integer[] arr, int left, int middle, int right) {
        // 临时数组 存储归并的信息
        Integer[] temp = new Integer[right - left + 1];
        // 缓存左数组第一个元素的索引 用于copy
        int tmp = left;
        // 左边数组第一个元素的索引位置
        int i = left;
        // 右边数组第一个元素的索引位置
        int j = middle + 1;
        // 记录临时数组的索引
        int k = 0;
        while (i <= middle && j <= right) {
            // // 从两个数组中取出最小的放入临时数组
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
//                arr[i] > arr[j]
                temp[k] = arr[j];
                j++;
            }
            k++;
        }
        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        while (i <= middle) {
            temp[k++] = arr[i++];
        }

        // 将临时数组中的内容拷贝回原数组中
        // （原left-right范围的内容被复制回原数组）
        for (int l = 0; l < temp.length; l++) {
            arr[tmp++] = temp[l];
        }

    }


    /**
     * 对数组进行归并
     *
     * @param arr
     * @param left
     * @param right
     * @param tempArr 临时数组,主要为了优化每次归并时开new新对象的问题
     */
    static void mergeSortV2(Integer[] arr, int left, int right, Integer[] tempArr) {

        /**
         *
         *
         * @import 优化思路一: 对于小数组, 使用插入排序优化
         *              if(right-left <= 15){插入排序 insertionSort(arr, left, right);}
         */
        if (right-left<=15) {
            insertSort(arr,left,right);
        }
//        if (right <= left) {
//            return;
//        }
        else {
            int middle = left + (right - left) / 2;
            // 对左侧序列进行归并排序
            mergeSortV2(arr, left, middle, tempArr);
            // 对右侧序列进行归并排序
            mergeSortV2(arr, middle + 1, right, tempArr);
            /**
             * @import 优化思路二
             *            如果 arr[middle] <= arr[middle+1] 则此时 arr是有序的,无需进行merge
             */
            if (arr[middle] > arr[middle + 1]) {
                // 合并两个子序列
                mergeV2(arr, left, middle, right, tempArr);
            }


        }
    }


    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     *
     * @param arr     目标数组
     * @param left    左边界
     * @param middle  中间
     * @param right   右边界
     * @param tempArr 临时数组 减少每次合并过程中数组的创建
     */
    static void mergeV2(Integer[] arr, int left, int middle, int right, Integer[] tempArr) {
        // 左数组的开始索引
        int i = left;
        // 右数组的开始索引
        int j = middle + 1;
        // 临时数组tempArr
        int k = 0;
        // 索引未越界时
        while (i <= middle && j <= right) {
            if (arr[i] < arr[j]) {
                tempArr[k++] = arr[i++];
            } else {
                tempArr[k++] = arr[j++];
            }
        }

        // 将左边剩余的元素添加到tempArr
        while (i <= middle) {
            tempArr[k++] = arr[i++];
        }

        // 将右边剩余的元素添加到tempArr
        while (j <= right) {
            tempArr[k++] = arr[j++];
        }

        // 将临时数组tempArr存储的值归并到arr
        for (int l = 0; l < k; l++) {
            arr[left++] = tempArr[l];
        }
    }


    /**
     * 对arr[left,right] 进行插入排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private static void insertSort(Integer[] arr, int left, int right) {
        // 从索引1开始 默认索引0是有序的
        for (int i = left + 1; i <= right; i++) {
            // 当前需要和i之前数组比较的值
            int curr = arr[i];
            // j为curr应该插入的位置
            int j;
            //  有序数组从最后一个元素开始和curr进行比较,如果大于curr则将该元素赋值给后一位元素
            for (j = i; j > left && arr[j - 1] > curr; j--) {
                arr[j] = arr[j - 1];
            }
            // 循环终止 代表找到了 j应该插入的位置
            arr[j] = curr;
        }
    }


    public static void main(String[] args) {
        int n = 10;
        Integer[] array = ArrayUtil.generateRandomArray(n, 0, n);
        ArrayUtil.printArray(array, 10);
        long start = System.nanoTime();
        sort(array);
        long end = System.nanoTime();
        double v = (end - start) / 1000000000.0;
        System.out.println("耗时: "+ v);
//        TestUtil.test(MergeSort.class, array);
        ArrayUtil.printArray(array, 10);

    }


}
